/*
 NChooseKSlates.c
 
 provides:
 StoredIndexVoteNode* createNChooseKSlateVote( StoredIndexVoteNode* vote, int numChoices, int seats );
 void enumerateNChoseKNameIndex( NameIndex* in, int numChoices, int seats, NameIndex* out );
 */

#include "NamedVotingSystem.h"
#include "NChooseKSlates.h"

#include <assert.h>
#include <string.h>

static int permuteSlate(
		StoredIndexVoteNode* in, int numChoices,
		int votePos, int* slatei, int depth, int depthLimit, int start, StoredIndexVoteNode* out ) {
	while ( start < numChoices ) {
		slatei[depth] = start;
		if ( depth == depthLimit ) {
			int i;
			double ratingSum = 0.0;
			assert(votePos < out->numVotes);
			// Add up the rating for everything in the in-vote that is in this slate permutation.
			for ( i = 0; i < in->numVotes; ++i ) {
				int j;
				int seats = depthLimit + 1;  // this is true. depthLimit passed to optimize more frequent test above.
				for ( j = 0; j < seats; ++j ) {
					if ( slatei[j] == in->vote[i].index ) {
						ratingSum += in->vote[i].rating;
						break;
					}
				}
			}
			out->vote[votePos].index = votePos;
			out->vote[votePos].rating = ratingSum;
			votePos++;
		} else {
			votePos = permuteSlate( in, numChoices, votePos, slatei, depth + 1, depthLimit, start + 1, out );
		}
	}
	return votePos;
}

/*
 Do combinatorial explosion to convert multi-seat election into single seat
 election where everyone is voting on fully elected slates behind the scenes.
 
 Based on ratings votes, a preference for a slate is the sum of the preference for the choices in it.
 */
StoredIndexVoteNode* createNChooseKSlateVote( StoredIndexVoteNode* vote, int numChoices, int seats ) {
	StoredIndexVoteNode* out;
	int* slatei;
	
	out = newStoredIndexVoteNode(NChooseK(numChoices, seats));
	if ( out == NULL ) {
		return NULL;
	}
	
	slatei = (int*)malloc(sizeof(int) * seats);
	if ( slatei == NULL ) {
		free(out);
		return NULL;
	}
	
	permuteSlate( vote, numChoices, 0, slatei, 0, seats - 1, 0, out );
	
	free(slatei);
	return out;
}

struct strbuf {
	char* buf;
	int len;
};

static int enumerateNChoseKNameIndexHelper(
		NameIndex* in, int numChoices, int votePos, int* slatei,
		int depth, int depthLimit, int start, struct strbuf* b, NameIndex* out ) {
	while ( start < numChoices ) {
		slatei[depth] = start;
		if ( depth == depthLimit ) {
			int j;
			int seats = depthLimit + 1;  // this is true. depthLimit passed to optimize more frequent test above.
			int newnamelen = 0;
			int newindex;
			// Add up the rating for everything in the in-vote that is in this slate permutation.
			for ( j = 0; j < seats; ++j ) {
				const char* jname = indexName(in, slatei[j]);
				int jlen = strlen(jname);
				if ((newnamelen + jlen + 2) > b->len) {
					b->len = newnamelen + jlen + 512;
					b->buf = (char*)realloc(b->buf, b->len);
					assert(b->buf);
				}
				strcpy(b->buf + newnamelen, jname);
				newnamelen += jlen;
				b->buf[newnamelen] = ',';
				newnamelen++;
			}
			newnamelen--;
			b->buf[newnamelen] = '\0';
			newindex = nameIndex( out, b->buf );
			assert(newindex == votePos);
			votePos++;
		} else {
			votePos = enumerateNChoseKNameIndexHelper( in, numChoices, votePos, slatei, depth + 1, depthLimit, start + 1, b, out );
		}
		start++;
	}
	return votePos;
}

/*
 Populate a NameIndex with the names and indecies that match what is generated by createNChooseKSlateVote().
 NameIndex must be empty before using this or createNChooseKSlateVote().
 */
void enumerateNChoseKNameIndex( NameIndex* in, int numChoices, int seats, NameIndex* out ) {
	struct strbuf b;
	int* slatei;

	b.len = 512;
	b.buf = (char*)malloc(b.len);
	assert(b.buf);

	slatei = (int*)malloc(sizeof(int) * seats);
	assert(slatei);

	enumerateNChoseKNameIndexHelper( in, numChoices, /*votePos*/0, slatei, /*depth*/0, /*depthLimit*/seats - 1, /*start*/0, &b, out );
	
	free(slatei);
	free(b.buf);
}
